package com.leetcode.math;

public class MaxSubArray {

    public static void main(String[] args) {

    }

    public int maxSubArray(int[] nums) {
        int sum = 0;
        int i = 0;
        int len = nums.length;
        int max = 0;
        int maxItem = nums[0];
        while(i < len) {
            if (nums[i] > 0) {
                sum += nums[i];
                if (sum > max) {
                    max = sum;
                }
            } else if (nums[i] < 0) {
                if (sum + nums[i] > 0) {
                    sum = sum + nums[i];
                } else {
                    sum = 0;
                }
            }
            if (nums[i] > maxItem) {
                maxItem = nums[i];
            }
            i++;
        }
        if (maxItem < 0) {
            max = maxItem;
        }
        return max;
    }
}
